Ví dụ NP-khó

Có rất nhiều bài toán NP-khó, chẳng hạn bài toán người bán hàng, cây Steiner nhỏ nhất, bài toán xếp ba lô, v.v...

Có những bài toán là NP-khó nhưng không phải NP-đầy đủ, chẳng hạn bài toán dừng. Bài toán này yêu cầu xác định xem với một chương trình và dữ liệu vào cho trước, liệu chương trình có chạy mãi mãi hay không.